1. Field of the Invention
This invention relates to a pseudorandom number generator using a shift register circuit, and more particularly to a pseudorandom number generator which can generate high-quality random numbers with a simple configuration.
2. Description of Related Technology
Uniformly distributed random number generators using a maximum length shift register sequence generator (hereinafter called M-sequence generator) are recently attracting attention. The M-sequence generator is that in which the constant polynomial is selected from the primitive polynomial on the Galois field, and in which the period of output sequence is maximized within the range where the constant polynomial has the same order. Of course, consideration must be given to manner in which the elements are taken out of the series generated by the M-sequence generator to use them as a random number. For instance, when random numbers are selected from an M-sequence {a.sub.i } as {a.sub.j, . . . , a.sub.j+k }, {a.sub.j+1, . . . , a.sub.j+k+1 }, {a.sub.j+2, . . . , a.sub.j+k+2 }, there is a strong correlation between consecutive random numbers, which is inadequate.
As dominant methods to generate uniformly distributed random numbers from an M-sequence, the Tausworthe method and the Lewis and Payne method are known.
In the Tausworthe method, an l-bit binary decimal EQU W.sub.i =0.a.sigma..sub.i+r-1 a.sigma..sub.i+r-2 . . . a.sub.it+r-l
is obtained by arranging l consecutive elements of the M-sequence {a.sub.i }, (l.ltoreq.p, p=dimension number of a constant polynomial), and it is made to be a random number. In the above equation, .sigma. is the distance at which l consecutive elements are taken out from the M-sequence. This method is summarized in FIG. 5. In random numbers thus generated, if the period T of the M-sequence and distance .sigma. are selected to be prime with each other, the cycle of {W.sub.i } also becomes T, and "0" appears 2.sup.p-l -1 times and each of other elements appears 2.sup.p-l times in a period. Therefore, if p is sufficiently larger than l, it is seen that these random numbers are uniformly distributed.
The Lewis and Payne method uses EQU f(D)=D.sup.p +D.sup.q +1 (p&gt;q)
as a characteristic equation, and a binary decimal EQU W.sub.i =0.a.sub.i a.sub.i +.tau..sub.2 . . . a.sub.i +.tau..sub.3
is obtained by taking out the elements of M-sequence {d.sub.i } at a suitable interval and arranging the resultant elements, and is made to be a random number. This method is summarized in FIG. 6. The M-sequence {a.sub.i } satisfies the recurrence formula: EQU a.sub.i =a.sub.i-p +a.sub.i-q (mod 2)
As the result, {W.sub.i } is produced by the recurrence formula: EQU W.sub.i =W.sub.i-p .sym.W.sub.i-q
where .sym. is the exclusive logic sum of each bit.
The above two methods, however, have serious faults. In the Tausworthe method, a long time is required to generate random numbers. In the Lewis and Payne method, the uniformity becomes ambiguous. The uniformity of random numbers is not guaranteed by this method itself, and the presence of uniformity must be reviewed.